package problems.daily.y2021m7;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author habitplus
 * @since 2021-07-03 08:49
 */
public class T20210703N1 {
    // 451. 根据字符出现频率排序
    // 给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
    public String frequencySort(String s) {
        // 计数 + 排序
        if (s == null || "".equals(s)) {
            return "";
        }

        int len = 65536;
        int[][] fre = new int[len][2];
        int t;
        for (int i = s.length() - 1; i >= 0; i--) {
            t = (int) s.charAt(i);
            fre[t][0] = t;
            fre[t][1]++;
        }

        Arrays.sort(fre, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });

        StringBuilder builder = new StringBuilder();
        char c;
        for (int i = len - 1; i >= 0 && fre[i][1] > 0 ; i--) {
            t = fre[i][1];
            c = (char) fre[i][0];
            while (t > 0) {
                builder.append(c);
                t--;
            }
        }

        return builder.toString();
    }

    public String frequencySort01(String s) {
        if (s == null || "".equals(s)) {
            return "";
        }

        int len = 65536;
        int[] fre = new int[len];

        int t;
        for (int i = s.length() - 1; i >= 0; i--) {
            t = (int) s.charAt(i);
            fre[t]++;
        }

        PriorityQueue<int[]> priorityQueue
                = new PriorityQueue<>((o1, o2) -> o2[1] - o1[1]);

        for (int i = 0; i < len; i++) {
            if (fre[i] > 0) {
                priorityQueue.offer(new int[]{i, fre[i]});
            }
        }

        StringBuilder builder = new StringBuilder();
        char c;
        while (!priorityQueue.isEmpty()) {
            int[] arr = priorityQueue.poll();
            t = arr[1];
            c = (char) arr[0];
            while (t > 0) {
                builder.append(c);
                t--;
            }
        }

        return builder.toString();
    }

    public static void main(String[] args) {
        System.out.println(new T20210703N1().frequencySort01("abcaba"));
    }
}
